Khi Chiến tranh thế giới thứ nhất nổ ra, trung đoàn của Paulus tham gia mũi tấn công vào nước Pháp. Một thời gian sau đó, ông là sĩ quan tham mưu phục vụ trong Quân đoàn Alpen (Alpenkorps) cho đến hết chiến tranh. Kết thúc Thế chiến I, ông mang quân hàm Đại úy.

Sau Hiệp ước Versailles, ông được chỉ định vào chức vụ Đại đội trưởng trong Trung đoàn Bộ binh 13 ở Stuttgart (1921-1933), rồi chỉ huy trưởng tiểu đoàn môtô cơ giới (1934-1935), trước khi trở thành Tham mưu trưởng Lực lượng Thiết giáp Panzer vào tháng 10 năm 1935, được phân công nhiệm vụ tổ chức và xây dựng 3 sư đoàn Panzer.

Tháng 5 năm 1939, ông được thăng Thiếu tướng (Generalmajor) và làm Tham mưu trưởng Tập đoàn quân X tấn công Ba Lan. Qua 2 chiến dịch, đơn vị được đổi thành Tập đoàn quân VI và chinh chiến qua các mặt trận Hà Lan và Bỉ.

Tháng 8 năm 1940, ông được thăng Trung tướng (Generalleutnant) và được cử làm Tham mưu phó Lục quân, và trên cương vị này ông tham gia việc trù định chiến dịch xâm lăng Nga. Tháng 1 năm 1942, ông là Tư lệnh Tập đoàn quân VI trong mũi tiến công đến Thành phố Stalingrad.